﻿// 0919train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using namespace std;

/*
 给定一个字符串的摘要算法，请输出给定字符串的摘要值
1. 去除字符串中非字母的符号
2. 对于去除非字母符号后的字符串：
  - 如果出现连续字符（不区分大小写），
  则输出: 该字母（小写) + 连续出现的次数
  - 如果是非连续的字符（不区分大小写），
  则输出: 该字母（小写）之后字符串中出现的该字符的次数
3. 对按照以上方式表示后的字符串进行排序：字母和紧随的数字作为一组进行排序
数字大的在前，数字相同的则按字母进行排序，字母小的在前

示例1
aabbcc
输出
a2b2c2

示例2
bAaAcBb
输出
a3b2b2c0

第一个b非连续字母，该字母之后字符串中还出现了2次 (最后的两个Bb) ，所以输出b2；
a连续出现3次，输出a3；
c非连续，该字母之后字符串再没有出现过c，输出c0；
Bb连续2次，输出b2。
对b2a3c0b2进行排序，最终输出a3b2b2c0
 */
class Solution01
{
public:
    bool isBig(char curr_ch)
    {
        return curr_ch >= 'A' && curr_ch <= 'Z';
    }
    bool isSmall(char curr_ch)
    {
        return curr_ch >= 'a' && curr_ch <= 'z';
    }
    Solution01(string&origin_str)
    {
        //去除字符串中非字母的符号
        string exec_str;
        for (auto&curr_ch:origin_str)
        {
            if (!isBig(curr_ch) && !isSmall(curr_ch))
                continue;
            if (isBig(curr_ch))
            {
                curr_ch = curr_ch - 'A' + 'a';
                exec_str += curr_ch;
            }
            else
            {
                exec_str += curr_ch;
            }
            //for
        }

        unordered_map<char, int>char_map;

        int str_size = exec_str.size();
        int right = str_size - 1;

        vector<pair<char, int>>result_v;
        while (right>=0)
        {
            char curr_ch = exec_str[right];
            int length = 1;
            for (int next=right-1; next>=0; next--)
            {
                if (exec_str[next] != curr_ch) break;
                length += 1;
            }
            if (length ==1)
            {
	            //非连续的字符,右边字符次数
                int count = 0;
                if (char_map.count(curr_ch)>0)
                {
                    count = char_map.at(curr_ch);
                }
                result_v.push_back(make_pair(curr_ch, count));

                //移动指针
                right -= 1;
                //统计次数
                char_map[curr_ch] += 1;
                continue;
            }
            result_v.push_back(make_pair(curr_ch, length));
            //移动指针
            right -= length;
            //统计次数
            char_map[curr_ch] += length;

            //while
        }

        //pair<char, int>
        //数字大的在前，数字相同的则按字母进行排序，字母小的在前
        sort(result_v.begin(), result_v.end(), [](pair<char, int>&p_1, pair<char, int>& p_2)
            {
                if (p_1.second==p_2.second)
                {
                    return p_1.first < p_2.first;
                }
                return p_1.second > p_2.second;
            });

        string result;
        for (auto&p_item:result_v)
        {
            result += p_item.first;
            result += to_string(p_item.second);
        }

        cout << result;
	    //Solution01
    }
};


/*
 输入描述
第一行为房间的X和Y (0 < X，Y <= 1000)
第二行为房间中墙壁的个数N (0 <= N < X*Y)
接着下面会有N行墙壁的坐标

输出描述
陷阱方格与不可达方格数量，两个信息在一行中输出,以一个空格隔开。(结尾不带回车换行)

输入
6 4
5
0 2
1 2
2 2
4 1
5 1
输出
2 3

机器人固定从方格(0, 0)出发，只能向东或者向北前进 
出口固定为房间的最东北角
如下图的方格(5, 3)。用例保证机器人可以从入口走到出口
 */
class Solution02
{
public:
    vector<vector<int>>getGrid(vector<vector<int>>& wall_v)
    {
        vector<vector<int>>grid(row_size_, vector<int>(col_size_));

        for (auto&pos:wall_v)
        {
            grid[pos[0]][pos[1]] = 1;
        }

        return grid;
        //getGrid
    }

    vector<vector<bool>>getChecked(vector<vector<int>>& wall_v)
    {
        vector<vector<bool>>checked(row_size_, vector<bool>(col_size_,false));

        for (auto& pos : wall_v)
        {
            //墙壁更新为true，方便计算不可到达
            checked[pos[0]][pos[1]] = true;
        }

        return checked;
        //getChecked
    }

    int checkUnavailable(vector<vector<int>>& wall_v)
    {
        vector<vector<int>>grid = getGrid(wall_v);

        //checked中为false的方格，不可到达
        vector<vector<bool>>checked = getChecked(wall_v);

        //只能向下或向右
        vector<vector<int>>DirectionGrid = { {1,0},{0,1} };

        deque<vector<int>>bfs_queue;
        bfs_queue.push_back({ 0,0 });
        checked[0][0] = true;

        while (!bfs_queue.empty())
        {
            vector<int>top_node = bfs_queue.front();
            bfs_queue.pop_front();

            for (auto&dir_v:DirectionGrid)
            {
                int curr_r = top_node[0] + dir_v[0];
                int curr_c = top_node[1] + dir_v[1];

                bool is_curr_r = curr_r >= 0 && curr_r < row_size_;
                bool is_curr_c = curr_c >= 0 && curr_c < col_size_;

                if (!is_curr_r || !is_curr_c) continue;

                bool is_visited = checked[curr_r][curr_c];

                if (!is_visited)
                {
                    bfs_queue.push_back({ curr_r,curr_c });
                    //标为已访问
                    checked[curr_r][curr_c] = true;
                }
	            //for
            }

            //while
        }

        checked_1 = checked;

        int count = 0;
        for (int r=0; r<row_size_; r++)
        {
	        for (int c=0; c<col_size_;c++)
	        {
                if (!checked[r][c]) count += 1;
	        }
        }
        return count;
        //checkUnavailable
    }


    int checkedDanger(vector<vector<int>>& wall_v)
    {
        vector<vector<int>>grid = getGrid(wall_v);
        vector<vector<bool>>checked = getChecked(wall_v);

        //两次checked，墙壁都为true
        //第一次为true，第二次为false的方格为danger

        deque<vector<int>>bfs_queue;
        bfs_queue.push_back({ row_size_ - 1, col_size_ - 1 });
        //标为已访问
        checked[row_size_ - 1][col_size_ - 1] = true;

        //只能向左向上
        vector<vector<int>>DirectionGrid = { {-1,0},{0,-1} };

        while (!bfs_queue.empty())
        {
            vector<int>top_node = bfs_queue.front();
            bfs_queue.pop_front();

            for (auto&dir_v:DirectionGrid)
            {
                int curr_r = top_node[0] + dir_v[0];
                int curr_c = top_node[1] + dir_v[1];

                bool is_curr_r = curr_r >= 0 && curr_r < row_size_;
                bool is_curr_c = curr_c >= 0 && curr_c < col_size_;

                if (!is_curr_r || !is_curr_c) continue;

                bool is_visited = checked[curr_r][curr_c];
                if (!is_visited)
                {
                    bfs_queue.push_back({ curr_r,curr_c });
                    //标为已访问
                    checked[curr_r][curr_c] = true;
                }
            }
	        //while
        }

        int count = 0;
        for (int r=0; r<row_size_;r++)
        {
            for (int c=0; c<col_size_; c++)
            {
                //checked_1为true，checked_2为false
                if (checked_1[r][c] && !checked[r][c])
                    count += 1;
            }
        }

        return count;
        //checkedDanger
    }


    Solution02(int row_size, int col_size, vector<vector<int>>&wall_v)
    {
        row_size_ = row_size;
    	col_size_ = col_size;

        int unavailable = checkUnavailable(wall_v);
        int danger = checkedDanger(wall_v);

        cout << danger << ' ' << unavailable;
	    //Solution02
    }
private:
    vector<vector<bool>>checked_1;
    int row_size_ = 0, col_size_ = 0;
};


int main()
{
	{
        int row_size, col_size, wall_v_size;
        cin >> row_size >> col_size >> wall_v_size;

        vector<vector<int>>wall_v(wall_v_size,vector<int>(2));

        for (int i=0; i<wall_v_size; i++)
        {
            cin >> wall_v[i][0] >> wall_v[i][1];
        }

        Solution02 solu(row_size, col_size, wall_v);

        return 0;
	}
    string origin_str;
    cin >> origin_str;

    Solution01 solu(origin_str);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
